using System;
using System.Collections.Generic;
using System.Text;
using Pacman.Simulator;

namespace Pacman.Implementations
{
	public class DijkstraPac : BasePacman
	{
		public DijkstraPac() : base("DijkstraPac","1") {			
		}

		StateInfo.PillPath avoidancePoint = null;
		LinkedList<DistanceNode> possibles;

		public override Direction Think(GameState gs) {
			Prediction prediction = new Prediction(gs, 15);

			// find new target (pill furthest away)			
			StateInfo.PillPath pillPath = StateInfo.FurthestPill(gs.Pacman.Node, gs);
			if( pillPath.PathInfo != null ) {
				avoidancePoint = pillPath;
			}		

			List<DirectionDanger> directionDangers = new List<DirectionDanger>();
			if( avoidancePoint != null ) {
				// run dijkstra to find path							
				foreach( Direction d in gs.Pacman.PossibleDirections() ) {
					// find best direction
					Direction bestDirection = Direction.None;
					float shortestRoute = float.MaxValue;
					possibles = new LinkedList<DistanceNode>();
					possibles.AddFirst(new LinkedListNode<DistanceNode>(new DistanceNode(gs.Pacman.Node.GetNode(d),0.0f,d,1)));
					while( possibles.Count > 0 ) {
						// find next lowest node
						DistanceNode node = possibles.First.Value;
						// found node
						if( node.Node == avoidancePoint.Target ) {
							if( node.Distance < shortestRoute ) {
								shortestRoute = node.Distance;
								bestDirection = d;								
							}
							break;
						}
						// pop node
						possibles.Remove(node);
						// add adjacents
						foreach( Node gn in node.Node.GhostPossibles[(int)node.Direction] ) {
							// find danger
							float danger = 0.0f;
							if( node.Time < prediction.Iterations ) {
								danger =	prediction.DangerMaps[node.Time+1].Danger[node.Node.X, node.Node.Y] +
											prediction.DangerMaps[node.Time+1].Danger[gn.X, gn.Y];
								if( danger > 1.0f ) {
									danger = 1.0f;
								}
							}
							// create new node
							DistanceNode newNode = new DistanceNode(gn, node.Distance + danger, node.Node.GetDirection(gn), node.Time + 1);
							// past iterations
							if( newNode.Time > prediction.Iterations ) {
								if( newNode.Distance < shortestRoute ) {
									shortestRoute = newNode.Distance;
									bestDirection = d;									
								}
								continue;
							}							
							LinkedListNode<DistanceNode> curNode = possibles.First;
							while( curNode != null && curNode.Value.Distance < newNode.Distance ){
								curNode = curNode.Next;
							}
							if( curNode == null ){
								possibles.AddLast(newNode);
							} else{
								possibles.AddAfter(curNode,newNode);
							}
						}
					}
					directionDangers.Add(new DirectionDanger(d, shortestRoute));
				}
			}
			// just take shortest path if it's somewhat safe
			StateInfo.PillPath globalPillPath = StateInfo.NearestPill(gs.Pacman.Node, gs);
			if( globalPillPath.PathInfo != null ) {
				foreach( DirectionDanger dd in directionDangers ) {
					if( dd.Direction == globalPillPath.PathInfo.Direction ) {
						if( dd.Danger < 0.1f ) {
							//Console.WriteLine("Pill: " + dd.Direction + " - " + dd.Danger);
							return globalPillPath.PathInfo.Direction;
						}
					}
				}
			}
			// else scramble
			Direction globalBestDirection = Direction.None;
			float bestDanger = 1.0f;
			foreach( DirectionDanger dd in directionDangers ) {
				if( dd.Danger <= bestDanger ) {
					bestDanger = dd.Danger;
					globalBestDirection = dd.Direction;
				}
			}
			//Console.WriteLine("Danger: " + globalBestDirection + " - " + bestDanger);
			return globalBestDirection;
		}
	}
}
